1. Field of the Invention
This invention relates generally to the methods and circuit implementation for performing an arithmetic addition operation. More particularly, this invention relates to a binary carry-select algorithm and the circuit design for implementation on an integrated circuit (IC) chip to achieve a faster addition operation.
2. Description of the Prior Art
An operation of adding two numbers to obtain the arithmetic sum thereof is a most common task routinely performed by modern data processors under various circumstances for different applications. Various algorithm and IC circuits are implemented to carry out this addition operation. Recent trend in computation technology requires ever increased rate of processing speed, i.e., higher through-put. An algorithm which has a feature capable of substantially increasing the speed of addition operations can be applied to a broad spectrum of applications to significantly improve the performance of a wide variety of computations.
One type of circuit for carrying out the adding operation is the `ripple-carry` circuit, wherein an adder is divided into many adder cells and each adder cell computes a sum and a carry for a bit or a bit group. After computing the sum and the carry in each adder cell, a carry output is serially transmitted from an adder cell for a least significant bit to an adder cell for a higher order bit. The time required for completing the computation of sum is essentially determined by the time for the carry signal to `ripple` through from the adder cell for the least significant to the most significant order of bits of the two adding operands. Due to the ripple effect, the computation time is delayed.
Another type of adders are the `carry-select` adders wherein two numbers each having many digits to be added are first divided into a plurality of corresponding digital groups. The adder for performing the summing operation is divided into adder cells each cell is to process a corresponding digital group. FIG. 1 shows such an adder cell 100. Each of the adder cells such as the adder cell 100 includes two double carry paths 102 and 104. Each carry path, 102 and 104, is used for an assumed carry signal 106 from the next less significant digital group which is either zero or one at the input side of the adder block. Among the carry paths 102 and 104 to be selected during the next data transmission is decided by employing a pair of carry-select multiplexers 108 (for sum) and 110 (for carry) using the block carry signal 106 of the preceding blocks. Two kinds of sums for each of the corresponding digital groups are thus processed first with the assumption that a `carry` 106 from the next less significant digital group is either one or zero. These sums for each of these digital groups are processed in parallel and a selection is made sequentially for each of these groups from the less to the more significant digital group if the sum is to be the value based on the assumption wherein the carry is either zero or one.
A more complicate application of the basic concept as depicted in FIG. 1 is an adder used for adding two operands of greater number of bits (or bit groups) as sown in FIG. 2. An adder 120 for adding two numbers is divided into many adder cells 125-1, 125-2, 125-3, etc. Each adder cell 125-i where i=1,2, 3 . . . , n processes a plurality of bits of two numbers, i.e., a.sub.0 a.sub.1 a.sub.2 a.sub.3 . . . a.sub.n and b.sub.0 b.sub.1 b.sub.2 b.sub.3 . . . b.sub.n. Except the first adder 125-1 for adding the least significant bit a0 to b0, every other adder cell has at least two full adders (FA) 128 denoted as FA(i,0) for calculating a sum and carry assuming the input carry i.e., the carryin 130, is zero, and FA(i,1) for calculating a sum and carry assuming the carryin 130, is one and where i denotes that the full adder is for processing bit the i-th bit.
Starting from the adder cell 125-1 for adding two least significant bits a.sub.0 and b.sub.0, the first full adder FA(0) generates a sum S(0) and a carry C(0). The carry C(0) is then transmitted to next adder cell 125-2 wherein FA(1,1) generates a sum s(1,1) and a carry c(1,1) and FA(1,0) generates a sum s(1,0) and a carry c(1,0). A pair of multiplexers MS-1 and MC-1 are used to process the sum and the carry for adding a.sub.1 and b.sub.1. Depending on the value of C(0), MS-1 selects s(1,1) or s(1,0) as the sum S(1) and similarly, MC-1 selects c(1,1) or c(1,0) as the carry C(1) to be transmitted to next adder cell 125-3.
In the adder cell 125-3, the summing operations are performed for bit-2 and bit-3. Two pairs of full adder FA(2,1), FA(2,0) and FA(3,1), FA(3,0) are used to generate corresponding sums, i.e., s(2,1) s(2,0), s(3,1),and s(3,0),and `carrys` c(2,1), c(2,0), c(3,1), and c(3,0). A sum multiplexer MS-3 and a carry multiplexer MC-3, which receive c(2,1) and c(2,0) as input, are then used to compute the sum S(3) and the carry C(3) for adder cell 125-3. MS-3 and MC-3 each has two output lines S.sub.o (3,1) and S.sub.o (3,0), and C.sub.o (3,1) and C.sub.o (3,0) respectively. Table 1 shows the selection of this pair of multiplexers.
TABLE 1 ______________________________________ TRUTH TABLE FOR MS-3 AND MC-3 c(2,1) c(2,0) S.sub.0 (3,1) S.sub.0 (3,0) C.sub.0 (3,1) C.sub.0 (3,0) ______________________________________ 0 0 S (3,0) S (3,0) C (3,0) C (3,0) 1 0 S (3,1) S (3,0) C (3,1) C (3,0) 1 1 S (3,1) S (3,1) C (3,1) C (3,1) ______________________________________
The output of MS-3 and MC-3 as represented by Table 1 can be derived from the fact that if c(2,1) and c(2,0) as computed by FA(2,1) and FA(2,0) respectively are both zero, then the sum and carry as computed by FA(3,0) are to be selected because now the carry is zero. Conversely, if c(2,1)=c(2,0)=1, then the sum and carry as computed by FA(3,1) are to be selected since the carry is one. However, if c(2,1) is one and c(2,0) is zero, then the carry and sum for the adder cell 125-3 is dependent upon the carry of the next less significant adder cell, i.e., C(1). A multiplexer MX-3 receives C(1) and S.sub.o (3,1), S.sub.o (3,0), C.sub.o (3,1), and C.sub.o (3,0) as input to process a sum S(3) and a carry C(3).
The combination of MS-3 and MC-3 constitute a fourplex processing means 135. The fourplex processing means 135 receives two carry-over input from a pair of full adders 128 for processing the next less significant bit and which also receives four output from a pair of full adders 128 for processing the current bit. The fourplex processing means generates the sum and the carry in accordance with Table 1.
In order to increase the through-put of the adder system 120, the next adder cell 125-4 makes use of the fourplex processing means 135 to process bits-4 to bit-6. The processing of bits-4 and bit-5 is identical to the process as described above for bit-2 and bit-3. Two carry output as generated by the fourplex processing means 135-5 for bit-5 are now inputted to the fourplex processing means 135-6 for bit-6 to generate a sum and carry for bit-6. In addition to the four input, the fourplex processing means 135-6 also receives a carry C(3) from last adder cell 125-3 to compute a sum S(6) and a carry C(6) to be carried over to next adder cell.
By the use of the same method and structure, next adder cell 125-5 processes bit-7 to bit-10. In order to more clearly show the structure of the adder 120 in the prior art, a simplified illustration is shown in FIG. 3. Only the structural portion for performing the operations of the `carry` for each pair of the full adder 128 is now shown as adder 128' and the fourplex processing means 135 is shown as one processing unit 135'. By referring to FIG. 3, it can be determined that the number of bits processed is increased by one from one adder cell to the next. It is also very clear for the structure of adder 120 the time required to process additional bits increase almost in a linear fashion because the need to wait for the receipt of the carry from the next less significant adder cell. For ease of reference, on the right hand side of each adder cell a number is also used in FIG. 3 to show the time cycles delay required for completion of the process of that adder cell. As the number of bits increased, the delay time is increased according to: EQU T.alpha.[1/2+(2N-7/4).sup.1/2 ] (1)
For the operation of adding two numbers with greater number of bits, the time cycles required for the adder 120 to complete the computation can become a bottle neck to a high speed processor when adding of two numbers of longer bit streams is performed frequently.
Therefore, a need still exits in the art to reduce the number of the time cycle delay in a carry select adder whereby the processing speed of the adder can be further improved which can be implemented to improve the performance level of different processes in a broad range of applications.